/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/add-and-search-word-data-structure-design
   @Language: C++
   @Datetime: 16-02-09 05:41
   */

class WordDictionary {
	struct TrieNode{
		static const int SIZE=26;
		TrieNode * child[SIZE+1];   // child[SIZE]='\0'
		TrieNode(){
			for(int i=0; i<=SIZE; child[i++]=NULL);
		}
		~TrieNode(){
			for(int i=0; i<=SIZE; ++i)
				if (child[i]) delete child[i];
		}
	};

	TrieNode *root=NULL;
	bool search(string &word, int begin, TrieNode *node){
		if(node==NULL) return false;
		for(int i=begin; i<word.length(); ++i){
			if (word[i]=='.'){
				bool found=false;
				for(int j=0; j<TrieNode::SIZE && !found; ++j)
					found=found || search(word,i+1,node->child[j]);
				return found;
			}
			else{
				node=node->child[word[i]-'a'];
				if(node==NULL) return false;
			}
		}
		return node->child[TrieNode::SIZE];
	}
public:
	WordDictionary(){
		root=new TrieNode();
	}
	~WordDictionary(){
		if (root) delete root;
	}
	/*
	 * @param word: Adds a word into the data structure.
	 * @return: nothing
	 */
	void addWord(string &word) {
		// write your code here
		if(word.length()<1) return;
		TrieNode *node=root;
		for(int i=0; i<word.length(); node=node->child[word[i]-'a'], ++i)
			if(node->child[word[i]-'a']==NULL)
				node->child[word[i]-'a']=new TrieNode();
		if(node->child[TrieNode::SIZE]==NULL)   // '\0'
			node->child[TrieNode::SIZE]=new TrieNode();
	}

	/*
	 * @param word: A word could contain the dot character '.' to represent any one letter.
	 * @return: if the word is in the data structure.
	 */
	bool search(string &word) {
		// write your code here
		return search(word,0,root);
	}
};
